package com.example.algorithm.no0213.impl;

import com.example.algorithm.no0213.Solution;

/**
 * @Description 动态规划
 * 时间复杂度 O(N) ： 遍历 nums 需要线性时间；
 * 空间复杂度 O(1) ： cur和 pre 使用常数大小的额外空间。
 * @ClassName DpSolution
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class RollSolutionImpl implements Solution {

    /**
     * {1,2,3,1}   4
     *
     * @param nums {1,2,3,1}
     */
    @Override
    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int size = nums.length;
        if (size == 1) {
            return nums[0];
        }
        if (size == 2) {
            return Math.max(nums[0], nums[1]);
        }

        return Math.max(robRange(nums, 0, size - 2), robRange(nums, 1, size - 1));
    }

    private int robRange(int[] nums, int begin, int end) {

        int pre = nums[begin];
        int curr = Math.max(nums[begin], nums[begin + 1]);
        int temp;

        for (int i = 2; i < end - begin + 1; i++) {
            temp = Math.max(curr, pre + nums[i]);
            pre = curr;
            curr = temp;
        }

        return curr;
    }
}
